In the field of robotics and automation there has recently been much interest in the problem of choosing paths for a set of objects so they do not collide. These methods are described, for example, in U.S. Pat. No. 4,949,277, in U.S. patent application Ser. No. 617,303 filed Nov. 16, 1990, U.S. patent application Ser. No. 646,516, filed Jan. 25, 1991 abandoned and U.S. patent application Ser. No. 392,636, filed Aug. 11, 1989 abandoned.
A simpler problem is collision detection, that is: the determination of whether or not a collision will occur when the paths and positions of objects are determined. Prior art collision detection algorithms are described in "A Study of The Clash Detection Problem in Robotics", S. Cameron, 1985, IEEE International Conference on Robotics and Automation, P. 488 et seq. which is incorporated herein as background material.
The prior art teaches that the size and shape of objects may be modeled as a series of overlapping circles (in two dimensions) or spheres (in three dimensions). These principles are described, for example, in "A Spherical Representation of The Human Body for Visualizing Movement", S. Badler et al, Proceedings of The IEEE, Vol. 67, No. 10, October 1979 and in published U.K. Patent Application 2,196,763A (May 5, 1988). The prior art also teaches that a hierarchy of such circles or spheres may be effectively used to represent the shape of an object in a data structure at varying levels of detail. See for example "Using an Efficient Collision Detector in The Solution of The Find Path Problem of Industrial Robots", Sawatzky, El-Zorkany, SPIE In Soc. Opt. Eng., Vol. 579, PP. 131-141 (1985).
The prior art also recognizes that, in some cases, the centers of spheres which were used to represent an object may be used to find the medial axis or skeleton of an object. See, for example, "Decomposition of Three-Dimensional Objects Into Spheres", O'Rourke and Badler, IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. PAMI-1, No. 3, July 1979.
In the description and claims which follow, spheres and circles of the above-mentioned data structure is referred to as a bubble hierarchy.
In a typical bubble hierarchy, the top or root of the hierarchy is a single spherical bubble, the enclosing bubble which encloses an entire object. This is the most coarse level of detail in the data structure. Within the top bubble, there are a small plurality of bubbles, each of which encloses a portion of the object and combined enclose the entire object. Within each of the bubbles at this second, successor level, there may be another plurality of bubbles, each of which encloses a smaller portion of the object. The expansion of bubbles to enclose finer level of detail continues until the bottom of the bubble hierarchy is reached. The bubbles at the bottom of the hierarchy each describe a small fragment of the object. In the simplest case, these bubbles are assumed to be solid; i.e. every point in the interior of such a bubble is assumed to be in the interior of the object.
A bubble hierarchy is useful for determining whether a point is inside or outside of an object and whether two objects (each represented by separate bubble hierarchies) intersect. The general technique for answering these questions is called bubble bursting. In a typical us of bubble bursting for determining whether a point is inside an object, a point-in-bubble test is first applied to the enclosing bubble. If this succeeds, (i.e., the point is found to be inside the enclosing bubble) then the bubble is burst, revealing the group of successor bubbles immediately below it in the hierarchy. The test is repeated with each of these bubbles. Wherever the test succeeds, the tested bubble is burst revealing the bubbles at the level immediately below it and those bubbles are tested. The procedure terminates if the point is found to be inside a bubble at the bottom of the hierarchy (in which case the point is inside the object) or if the point is found to be outside all the remaining bubbles after a certain number have been burst.
While techniques for using bubbles to plan and control the motion of machines and robots are well-known in the art, the problem of finding an optimum placement of bubbles to represent a given object remains. Computational time can be decreased and machine speed increased if an optimal bubble placement is determined, yet many bubble placement methods which have been suggested in the prior art operate efficiently in two dimensional systems but which become complex and time consuming when expanded to the representation of three dimensional objects and systems.